package com.example.demo.sort;

import java.util.Arrays;

/**
 * 快速排序
 * <p>
 * 思路： <br>
 * 1. 采用分治的思想来进行处理。 <br>
 * 2. 首先找出一个基准元素pivot（一般为数组的第一个元素）。 <br>
 * 3. 然后遍历数组，把比基准元素pivot小的元素放在元素的左边，把比基准元素大的元素pivot放在元素的右边。并返回最后基准元素所在的下标。 <br>
 * 4. 然后递归的把小于基准元素的子数组和大于基准元素的子数组重复第三部的操作。 <br>
 * <p>
 * 时间复杂度：O(nLogn)<br>
 * 空间复杂度：O(1)
 *
 * @author WangYX
 * @version 1.0.0
 * @date 2024/01/26 11:30
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] a = {1, 123, 423, 5345, 46, 24, 234, 23423, 64, 56, 567, 77, 45645};
        long l = System.currentTimeMillis();
        QuickSort(a, 0, 6);
        long l1 = System.currentTimeMillis();
        System.out.println(l1 - l);

        String s = Arrays.toString(a);
        System.out.println(s);
    }

    /**
     * 快速排序算法
     *
     * @param array
     * @param low
     * @param hight
     */
    public static void QuickSort(int[] array, int low, int hight) {
        if (array.length < 1 || low < 0 || hight >= array.length || low > hight) {
            return;
        }
        if (low < hight) {
            //把数组分块
            int privotpos = partition(array, low, hight);
            //基准元素左边递归
            QuickSort(array, low, privotpos - 1);
            //基准元素右边递归
            QuickSort(array, privotpos + 1, hight);
        }
    }

    public static int partition(int[] array, int low, int hight) {
        // 选取第一个为基准元素
        int privot = array[low];
        while (low < hight) {
            /* 先从右往左移动，直到遇见小于 pivot 的元素 */
            while (low < hight && array[hight] >= privot) {
                hight--;
            }
            // 记录小于 pivot 的值,记录在low的位置
            array[low] = array[hight];

            /* 再从左往右移动，直到遇见大于 pivot 的元素 */
            while (low < hight && array[low] <= privot) {
                low++;
            }
            // 记录大于 pivot 的值，记录在height的位置
            array[hight] = array[low];
        }

        // 记录基准元素的值到当前指针（low，height）共同指向的区域
        array[low] = privot;

        // 返回基准元素的下标
        return low;
    }
}
